package th.retrofit.lib;

import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;

/**
 * https://leetcode-cn.com/problems/maximal-rectangle/
 * 给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。
 */
public class Solution85 {
    public int maximalRectangle(char[][] matrix) {
        int row = matrix.length;
        if (row == 0) return 0;
        int col = matrix[0].length;
        int maxArea = 0;
        int[] heights = new int[col];
        for (char[] chars : matrix) {
            for (int j = 0; j < col; j++) {
                if (chars[j] == '0') {
                    heights[j] = 0;
                } else {
                    heights[j] += 1;
                }
            }
            maxArea = Math.max(maxArea, largestRectangleArea(heights));
        }
        return maxArea;
    }

    public int largestRectangleArea(int[] heights) {
        int hLen = heights.length;
        int maxArea = 0;
        Deque<Integer> stack = new LinkedList<>();
        for (int i = 0; i < hLen; i++) {
            while (!stack.isEmpty() && heights[i] < heights[stack.peekLast()]) {
                int left = stack.pollLast();
                int width = i - (stack.isEmpty() ? -1 : stack.peekLast()) - 1;
                maxArea = Math.max(maxArea, width * heights[left]);
            }
            stack.offerLast(i);
        }
        while (!stack.isEmpty()) {
            int height = heights[stack.pollLast()];
            int width = hLen - (stack.isEmpty() ? -1 : stack.peekLast()) - 1;
            maxArea = Math.max(maxArea, width * height);
        }
        return maxArea;
    }

    public static void main(String[] args) {
        char[][] matrix = new char[][]{
                {'1','0','1','0','0'},
                {'1','0','1','1','1'},
                {'1','1','1','1','1'},
                {'1','0','0','1','0'}
        };
        System.out.println(new Solution85().maximalRectangle(matrix));
    }
}
